package com;

import sun.reflect.generics.tree.Tree;

import java.util.*;

public class Main {

    private static int maxAcrossRoot = Integer.MIN_VALUE;

    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        node1.left = node2;
        node1.right = node3;
        node2.left = new TreeNode(4);
        node2.right = new TreeNode(5);
        node3.left = new TreeNode(6);
        node3.right = new TreeNode(7);
        int endAtRoot = maxPath(node1);
        System.out.println(Math.max(endAtRoot, maxAcrossRoot));
    }

    public static int maxPath(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = maxPath(root.left);
        int right = maxPath(root.right);
        int val = root.val;
        if (left > 0) {
            val += left;
        }
        if (right > 0) {
            val += right;
        }
        maxAcrossRoot = Math.max(maxAcrossRoot, val);
        return Math.max(Math.max(root.val + left, root.val + right), root.val);
    }

}

class Node {
    int val;
    Node next;

    public Node(int val) {
        this.val = val;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
}

